"""
Sample solutions to the second problem of the June 2012 exam.
"""

dbg = False #debug mode

def aire_it(liste):
    """
    Only precondition: clockwise order.
    Shorter and faster iterative version of aire()...
    """
    cp = liste[:] #copy to be altered (almost destroyed, actually)...
    acc = 0 #surface accumulator
    while len(cp)>2: #any triangle left?
        #base case. *.5 is used to avoid another function call (this line has enough nested terms)
        acc += abs((cp[1][0]-cp[0][0])*(cp[2][1]-cp[0][1])-(cp[2][0]-cp[0][0])*(cp[1][1]-cp[0][1]))*.5
        #delete the "middle point"
        del cp[1]
    return acc

def aire(liste, lvl=0):
    """Preconditions: clockwise order, at least 3 points."""
    if len(liste)<3:
        if dbg: print "  "*lvl+("precond %s"%liste)
        raise ValueError("Violated precondition len(liste)>3")
        #another precondition that should be checked is the clockwise order!
    elif len(liste)==3:
        #base case. *.5 is used to avoid another function call (this line has enough nested terms)
        if dbg: print "  "*lvl+"base case", liste
        return abs((liste[1][0]-liste[0][0])*(liste[2][1]-liste[0][1])-(liste[2][0]-liste[0][0])*(liste[1][1]-liste[0][1]))*.5
    else:
        mid = len(liste) / 2 #integer division
        #we'll use p1=0, p2=mid to make things easier...
        if dbg: print "  "*lvl+("need [:%d+1] and [0]&[%d:]" % (mid, mid))
        if dbg: print "  "*lvl+"first"
        ret = aire(liste[:mid+1], lvl+1)
        if dbg: print "  "*lvl+"second"
        ret += aire([liste[0]]+liste[mid:], lvl+1) #order IS important!
        if dbg: print "  "*lvl+"done"
        return ret


#Proudly exported from GeoGebra with vim!
pts = [(1.24, 4.08),(3.06, 5.22),(4.28, 4.72),
        (4.52, 3.42),(3.8, 2.7),(2.92, 2.54),
        (2.64, 0.4),(2.2, 0.16),(1.5, -0.08),
        (1.06, 0.2),(0.5, 0.7),(0.48, 1.02),
        (0.44, 1.54),(0.64, 2.64),(0.96, 3.72),]

ggb = 12.61
print "GeoGebra: %.2f" % ggb
print "recursive+delta: %.2f, %.2f" % (aire(pts), abs(ggb-aire(pts)))
print "iterative+delta: %.2f, %.2f" % (aire_it(pts), abs(ggb-aire_it(pts)))
